package com.chapter4.graph.undirect;

import com.chapter4.graph.undirect.Graph;

/** 
 * @ClassName: TwoColor 
 * @Description: 是否是二分图
 * @author minjun minjun@bw30.com
 * @date 2015-2-26 上午7:55:33 
 *  
 */
public class TwoColor {

	private boolean[] marked;
	
	private boolean[] color;
	
	private boolean isTwoColor=true;
	
	public TwoColor(Graph g){
		int len=g.V();
		marked=new boolean[len];
		color=new boolean[len];
		for(int i=0;i<len;i++){
			if(!marked[i]){
				dfs(g,i);
			}
		}
	}

	/** 
	* @Title: dfs 
	* @Description: dfs
	* @param @param g
	* @param @param i    设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	private void dfs(Graph g, int v) {
		marked[v]=true;
		for(int w:g.adj(v)){
			if(!marked[w]){
				color[w]=!color[v];
				dfs(g,w);
			}else if(color[v]==color[w]){
				isTwoColor=false;
			}
		}
	}
	
	public boolean isBipartite(){
		return isTwoColor;
	}
}
